package me.eg.fifth;

/**
 * 74. 搜索二维矩阵
 * <p>
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix
 */
public class SearchMatrix {
    /**
     * 解法一：2次二分查找
     * 时间复杂度：O(logMN)
     * 空间复杂度：O(1)
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = -1, right = m - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (matrix[mid][0] <= target) left = mid;
            else right = mid - 1;
        }
        if (right < 0) return false;

        int row = right;
        left = 0;
        right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (matrix[row][mid] == target) return true;
            if (matrix[row][mid] > target) right = right - 1;
            else left = mid + 1;
        }
        return false;
    }

    /**
     * 解法二：一次二分查找，二维转一维
     * 时间复杂度：O(logMN)
     * 空间复杂度：O(1)
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix_1(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            // 二维转一维 pos = r * n + c
            // 一维转二维 r = pos / n, c = pos % n
            int num = matrix[mid / n][mid % n];
            if (num == target) return true;
            if (num > target) right = mid - 1;
            else left = mid + 1;
        }
        return false;
    }
}